1. Field of the Invention
The present invention relates generally to arbitration routing systems and, more particularly, to arbitration of mutually exclusive resources.
2. Description of Related Art
Network devices, such as routers, relay data through a network from a source to a destination. The data may be in the form of packets. Typically, the network devices include one or more arbitration subsystems to control data flow among various queues and/or buffers (hereinafter “queues”) or other resources.
FIG. 1 is a diagram of an arbitration subsystem 100 that routes data to a number of different queues. Arbitration subsystem 100 may include a number of first-in-first-out (FIFO) queues 110, an arbiter 120, a first destination queue 130, a second destination queue 140, and a third destination queue 150. The subsystem may include fewer than (e.g., two) or more than (e.g., four or more) the three destination queues 130-150. FIFO queues 110 may receive data from a number (e.g., 256) of different streams (not shown). Arbiter 120 may be configured to perform arbitration among FIFO queues 110 and send the chosen data to one of destination queues 130-150. Typically, arbiter 120 performs a certain type of arbitration (e.g., round robin) to pick one FIFO queue 110 and then routes the data in the FIFO queue based on some criteria (e.g., packet size of the data). Other criteria are possible for the routing function of the arbiter 120.
For example, in FIG. 1, the arbiter 120 may send packets larger than a first threshold to the first destination queue 130. The arbiter 120 may send packets smaller than a second threshold (that is smaller than the first threshold) to the third destination queue 150 and send packets smaller than the first threshold but larger than the second threshold to the second destination queue 140. Because each piece of data (e.g., packet) in the FIFO queues 110 may be sent to only one of the destination queues 130-150, the data contained in FIFO queues 110 may be viewed as three mutually exclusive vectors, each corresponding to one of the three destination queues 130-150. Each bit in a particular vector corresponds to a FIFO queue 110, and the bit may be set to “1” if the data waiting for servicing in the FIFO queue 110 is destined for the queue (e.g., first destination queue 130) corresponding to that particular vector. Use of such mutually exclusive vectors enables the arbiter 120 to perform the routing of data after performing arbitration.
FIG. 2 illustrates two such mutually exclusive vectors 210 and 220, for ease of explanation. The position of the last FIFO queue serviced by the arbiter 120 is denoted as X. The position of the next queue to service in vector 210 is denoted by A. The position of the next queue to service in vector 220 is denoted by B. The arbiter 120 may determine which of positions A and B to service next in accordance with, for example, a round-robin scheme. In such a round-robin scheme, the next queue may be the closest to the right of position X. However, difficulties arise because the positions of the vectors 210 and 220 “wrap” around when the end of the vector is reached. Hence, the arbiter 120 cannot simply choose, for example, the larger-numbered of positions A and B as the closest position to position X.
FIG. 3 illustrates an implementation of the arbiter 120 that performs round robin arbitration on the two mutually exclusive vectors in FIG. 2. The arbiter 120 may include a first vector arbiter 310, a second vector arbiter 320, three subtracting elements 330, and a logic block 340. The first vector arbiter 310 may perform round robin arbitration on the first vector 210 to identify position A within the vector, and the second vector arbiter 310 may perform round robin arbitration on the second vector 220 to identify position B within the vector. The three subtracting elements 330 may perform A-X, A-B, and B-X to produce three positional differences. The logic 340 may be configured to determine the position Y of the next queue to be serviced based on the three positional differences. The third positional difference, A-B, is required to determine which of A and B is directionally closer to X, the last queue serviced.
FIG. 4 illustrates an implementation of the arbiter 120 that performs round robin arbitration on three mutually exclusive vectors. The arbiter 120 may include a first vector arbiter 410, a second vector arbiter 420, a third vector arbiter 430, six subtracting elements 440, and a logic block 450. The elements in FIG. 4 operate similarly to the corresponding elements in FIG. 3, and will not be further described, with the exception of the subtracting elements 440. When the number of mutually exclusive vectors increases to three, six subtracting elements 440 are needed to determine which of positions A, B, and C is directionally closer to the last queue X. The addition of the third vector necessitates the three additional subtracting elements to determine C-X, B-C, and C-A. The logic block 450 decides among the six positional differences produced by the subtracting elements 440 and will be much more complex than the logic block 340 due to the addition of the third vector 230.
The added complexity of the subtracting elements 440 and the logic block 450 illustrate that the arbiter design in FIGS. 3 and 4 grows in complexity with the addition of more vectors. In other words, this design does not scale well with increasing numbers of vectors. Further, the delay that the arbiter 120 shown in FIGS. 3 and 4 introduces to find the next queue Y is equal to the delay associated with the vector arbiters, plus a delay associated with the subtracting elements, plus a delay associated with the logic block. The subtracting elements (e.g., 330) and the logic block (e.g., 340) may contribute significantly to the overall delay associated with the arbiter 120.
Accordingly, there exists a need for systems and methods for arbitrating across mutually exclusive vectors (e.g., destination queues) that scale well with increasing numbers of vectors and that minimize delay associated with the arbitration.